package sjjg.sort;


class 荷兰国旗问题 {
    public static void main(String[] args) {
        int arr[] = {1, 3, 2, 4, 5};
        solve1(arr, 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void solve1(int arr[], int target) {
        int borderL = 0;
        int borderR = arr.length - 1;
        int i = 0;
        while (i != borderR) {
            if (arr[i] < target) {
                if (borderL != i) swap(arr, i, borderL);
                borderL++;
                i++;
            } else if (arr[i] == target) {
                i++;
            } else {
                swap(arr, i, borderR--);
            }
        }
    }

    public static void solve(int arr[], int target) {
        int border = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] <= target) {
                if (border != i)
                    swap(arr, border++, i);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

public class quick_sort {
    public static void main(String[] args) {
        int arr[] = {9, 8, 7, 6, 5, 4, 3, 1, 2};//1 5 2 4 3   1 4 2 5 3  1     2 4 5 3 3  2 3 3 5 4
        quickSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void quickSort(int[] arr) {
        int low = 0;
        int height = arr.length - 1;
        quickSort(arr, low, height);
    }

    /*快排3.0*/
    private static void quickSort(int[] arr, int low, int height) {
        if (low >= height) return;
        //分区
        int[] border = partion(arr, low, height);
        //对左区进行递归快排
        quickSort(arr, low, border[0] - 1);
        //对右区进行递归快排
        quickSort(arr, border[1] + 1, height);
    }

    private static int[] partion(int[] arr, int low, int height) {
        int random = low + (int) (Math.random() * (height - low + 1));
        System.out.println(random);
        random = arr[random];
        int i = low;
        int borderL = low;
        int borderR = height;
        while (i <= borderR) {
            if (arr[i] < random) {
                swap(arr, i++, borderL++);
            } else if (arr[i] == random) {
                i++;
            } else {
                swap(arr, i, borderR--);
            }
        }
        return new int[]{borderL, borderR};
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
   /* public static void quickSort(int []arr,int low,int height){
           //退出条件
        if(low>=height)return;
        //分区 左边的数都小于arr[low] 右边的数都大于arr[low](最后返回arr[low]所在下标)
        int left=low;
        int right=height+1;
        while (true){
            //从左往右找到一个比arr[low]大的数
            while (arr[++left]<=arr[low]){
                if(left>=height){
                    break;
                }
            }
            //从右往左找到一个比arr[low]小的数
            while (arr[--right]>=arr[low]){
                if(right<=low){
                    break;
                }
            }
            if(left>=right){
                //此时说明已经遍历完成 退出循环
                break;
            }else {
                //此时说明已经找到左边一个数是大于arr[low]的，右边一个数是小于arr[row]的 交换
                int temp=arr[left];
                arr[left]=arr[right];
                arr[right]=temp;
            }
        }
        //退出循环后交换arr[right] 与 arr[low] 的值 使其完成真正的分区
        int temp=arr[right];
        arr[right]=arr[low];
        arr[low]=temp;
        quickSort(arr,low,right-1);//递归调用
        quickSort(arr,right+1,height);//递归调用
    }*/
}
